package leetcode.code787.CheapestFlightsWithinKStops;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 超出内存限制
 *
 * @author Max
 * @date 2021年8月24日
 * @description
 */
public class Solution78704 extends CheapestFlightsWithinKStops {

	@Override
	public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
		Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
		for (int[] flight : flights) {
			if (map.containsKey(flight[0])) {
				Map<Integer, Integer> temp = map.get(flight[0]);
				temp.put(flight[1], flight[2]);
			} else {
				Map<Integer, Integer> temp = new HashMap<>();
				temp.put(flight[1], flight[2]);
				map.put(flight[0], temp);
			}
		}
		int max = 1000001;
		int min = max;
		int[][] dp = new int[n][k + 1];
		Queue<Integer> s = new LinkedList<>();
		Queue<Integer> b = new LinkedList<>();
		s.add(src);
		int step = 0;
		while (step <= k) {
			while (!s.isEmpty()) {
				int start = s.poll();
				Map<Integer, Integer> m = map.get(start);
				if (m != null)
					for (Integer p : m.keySet()) {
						if (step == 0)
							dp[p][step] = m.get(p);
						else {
							if (dp[p][step] == 0) {
								dp[p][step] = m.get(p) + dp[start][step - 1];
							} else
								dp[p][step] = Math.min(dp[p][step], m.get(p) + dp[start][step - 1]);
						}
						b.add(p);
					}
			}
			s.addAll(b);
			b.clear();
			if (dp[dst][step] != 0)
				min = Math.min(min, dp[dst][step]);
			step++;
		}
		return min == max ? -1 : min;
	}

	public static void main(String[] args) {
		Solution78704 so = new Solution78704();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
